#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Student
{
	int num;
	char name[50];
	struct Student *left;
	struct Student *right;
};
typedef struct Student student;

student *new(int num, char *name)//生成节点
{
	student *newp;
	newp = (student *)malloc(sizeof(student));
	memset(newp, 0, sizeof(newp));
	strcpy(newp->name, name);
	newp->num = num;
	return newp;
}

student *insert(student *treep, student *newp)//插入节点
{
	int cmp = 0;
	if (treep == NULL)
		return newp;
	cmp = strcmp(newp->name, treep->name);
	if (cmp == 0)
		printf("insert error: %s\n", newp->name);
	else if (cmp < 0)
		treep->left = insert(treep->left, newp);
	else 
		treep->right = insert(treep->right, newp);
	return treep;
}

student *lookup(student *treep, char *name)//查找节点
{
	int cmp = 0;
	if (treep == NULL)
		return;
	cmp = strcmp(treep->name, name);
	if (cmp == 0)
		{
			printf("treep->name: %s\n", treep->name);
			return treep;
		}
	else if(cmp < 0)
		lookup(treep->left, name);
	else 
		lookup(treep->right, name);
}

int deletechild(student *treep)
{
	if (! treep)
		return 0;
	if (treep->left)
		deletechild(treep->left);
	if (treep->right)
		deletechild(treep->right);
	free(treep);
	treep = NULL;
	return 1;
}


student *delete(student *treep, char *name)//删除子树
{
	int cmp = 0;
	student *p1, *p2;
	p2 = p1;
	cmp = strcmp(treep->name, name);
	if (cmp == 0)
	{
		p1 = treep;
		if (strcmp(p1->name, p2->name) < 0)
			printf("left\n");
		else 
			printf("right\n");
		deletechild(p1);
		return treep;
	}
	else if (cmp < 0)
		delete(treep->left, name);
	else 
		delete(treep->right, name);
}

void printp(student *treep, void *arg)//打印树
{
	char *fmt = (char *) arg;
	printf(fmt, treep->name, treep->num);
	
}


void print(student *treep, void(*fn)(student *treep, void *arg), void *arg)
{
	if (treep == NULL)
		return;
	print(treep->left, fn, arg);
	(*fn)(treep, arg);
	print(treep->right, fn, arg);
}


int main()
{
	student *treep = NULL;
	treep = new(50, "lzb");
	treep = insert(treep, new(55, "liaoddao"));
	treep = insert(treep, new(13, "ouge"));
	treep = insert(treep, new(14, "oouge"));
	print(treep, printp, "name: %s, num: %d\n");
	lookup(treep, "lzb");
	treep = delete(treep, "oouge");
	print(treep, printp, "name: %s, num: %d\n");
	return 0;
}
